package line;

/**
 * 线性表顺序存储结构 用数组表示线性表的顺序存储结构,类型为Object 
 * 变量data用于顺序存放数据 
 * 变量current表示当前线性表存放元素数量
 * 变量capacity表示线性表容量
 * @author mengxin
 * @param <E>
 */
public class ArrayList<E> {
	private Object[] data = null;// 用数组表示的线性表,保存实际数据
	private int current = 0;// 线性表元素数量
	private int capacity = 0;// 线性表容量

	/**
	 * 如果初始化时，未声明大小，则默认为10
	 */
	public ArrayList() {
		this(10);
	}

	/**
	 * 初始化线性表，并且声明保存内容的数组大小
	 * @param initalSize
	 */
	public ArrayList(int initalSize) {
		if (initalSize < 0) {
			throw new RuntimeException("线性表大小错误:" + initalSize);
		} else {
			this.data = new Object[initalSize];
			this.current = 0;
			capacity = initalSize;
		}
	}

	/**
	 * 添加元素的方法,添加前,先确认是否已满
	 * @param e
	 * @return
	 */
	public boolean add(E e) {
		ensureCapacity(current);// 确认容量
		this.data[current] = e;
		current++;
		return true;
	}

	/**
	 * 确认系统当前容量是否满足需要,如果满足，则不执行操作 如果不满足，增加容量一倍
	 * @param cur 当前个数
	 */
	private void ensureCapacity(int cur) {
		if (cur == capacity) {
			// 如果达到容量极限，增加10的容量，复制当前数组
			this.capacity = 2 * this.capacity;
			Object[] newdata = new Object[capacity];
			for (int i = 0; i < cur; i++) {
				newdata[i] = this.data[i];
			}
			this.data = newdata;
		}
	}

	/**
	 * 得到指定下标的数据
	 * @param index
	 * @return
	 */
	public E get(int index) {
		validateIndex(index);
		return (E) this.data[index];
	}

	/**
	 * 返回当前线性表元素数量
	 * @return
	 */
	public int size() {
		return this.current;
	}
	
	/**
	 * 获取线性表容量
	 * @return
	 */
	public int capacity(){
		return this.capacity;
	}

	/**
	 * 更改指定下标元素的数据为e
	 * @param index
	 * @param e
	 * @return
	 */
	public boolean set(int index, E e) {
		validateIndex(index);
		this.data[index] = e;
		return true;
	}
	
	public void delete(int index){
		validateIndex(index);
		for(int i=index;i<current;i++){
			this.data[i]=this.data[i+1];
		}
	}

	/**
	 * 验证当前下标是否合法，如果不合法，抛出运行时异常
	 * @param index 下标
	 */
	private void validateIndex(int index) {
		if (index < 0 || index > current) {
			throw new RuntimeException("数组index错误：" + index);
		}
	}

	/**
	 * 在指定下标位置处插入数据e
	 * @param index 下标
	 * @param e 需要插入的数据
	 * @return
	 */
	public boolean insert(int index, E e) {
		validateIndex(index);
		Object[] tem = new Object[capacity];// 用一个临时数组作为备份
		// 开始备份原始线性表
		for (int i = 0; i < capacity; i++) {
			if (i < index) {
				tem[i] = this.data[i];
			} else if (i == index) {
				tem[i] = e;
			} else if (i > index) {
				tem[i] = this.data[i - 1];
			}
		}
		this.data = tem;
		return true;
	}
	
	@Override
	public String toString() {
		StringBuffer sb = new StringBuffer();
		for(int i=0;i<this.capacity();i++){
			sb.append("[");
			sb.append(this.data[i]);
			sb.append("]");
		}
		return sb.toString();
	}

	public static void main(String[] args) throws Exception{
		ArrayList<Integer> array = new ArrayList<Integer>(10);
		for(int i=0;i<array.capacity()-1;i++){
			array.add(i);
		}
		System.out.println(array.toString());
		System.out.println("线性表容量"+array.capacity()+",线性表当前元素数量"+array.size());
		System.out.println("位置4数据"+array.get(4));
		array.set(3, 13);
		System.out.println("位置3更改后数据"+array.get(3));
		array.insert(3, 103);
		System.out.println(array.toString());
		array.delete(3);
		System.out.println(array.toString());
	}
}
